package medium

import (
	. "GoLeetcode/common"
	"sort"
)

/*

时间复杂度:O(NlogN) 排序的时间消耗
空间复杂度:O(logN) 排序所需要的内存
*/

func maxFrequency(nums []int, k int) int {
	// left表示窗口左边界下表，right表示窗口右边界下标
	// preSum表示窗口内所有值都变换到与窗口最右边的值相同时，所需要的操作次数
	// ans表示操作最多k次后出现次数最多的数
	left, right, preSum, ans := 0, 1, 0, 1

	// 先将所有数进行排序
	sort.Ints(nums)
	for right < len(nums) {
		// right-left表示总共需要操作的数字个数
		// nums[right] - nums[right-1]，由于每次右边界往右边移动，其实倒数第二个元素其左边所有元素都已经操作到跟倒数第二个元素相同
		// 之后当新的元素从右窗口进来，只需要考虑将窗口内右边界元素左边的所有元素都转换为右边界元素
		preSum += (right - left) * (nums[right] - nums[right-1])
		for preSum > k {
			preSum -= nums[right] - nums[left]
			left++
		}
		ans = Max(ans, right-left+1)
		right++
	}
	return ans
}